Tree, Heap, &
Geometri Dasar
👩🏫 Secara Formal:
OSN tidak hanya menguji data linear seperti Array. Kadang data memiliki hierarki (seperti pohon) dan posisi di ruang Kartesius (Geometri).
- Tree (Pohon): Struktur data non-linear berhierarki. Memiliki Root (akar paling atas), Node (titik), dan Leaf (daun terbawah yang tidak punya anak).
- Binary Search Tree (BST): Pohon di mana anak KIRI selalu lebih KECIL dari induknya, dan anak KANAN selalu lebih BESAR.
- Geometri (Jarak Euclidean): Jarak terpendek (garis lurus) antara dua titik $(x_1, y_1)$ dan $(x_2, y_2)$. Dihitung menggunakan rumus Pythagoras: $d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$.
Analogi Jaman Now
Tree (Pohon Hierarki)
Bayangin Struktur Folder di Laptop/PC kamu. Drive C: adalah *Root*. Di dalamnya ada folder "Program Files", "Windows", dll (ini *Node* anak). Kalau foldernya sudah kosong cuma isi file biasa, itu namanya *Leaf* (Daun).
Jarak Euclidean
Kayak narik Garis Lurus di Google Maps (jarak burung terbang) dari titik A ke titik B, menembus gunung dan gedung. Berbeda dengan *Manhattan Distance* yang harus belok-belok ngikutin blok jalan raya kota.
Kalkulator Jarak Euclidean
Geser titik merah (A) dan biru (B) di dalam koordinat Kartesius. Lihat bagaimana rumus Pythagoras bekerja untuk mencari jarak garis lurus di antara keduanya.
⚠️ Common Mistakes: Overflow & Presisi Floating Point
Dalam Competitive Programming (OSN), menghitung Jarak Euclidean sering menjebak siswa dengan dua hal:
1. Integer Overflow: Jarak koordinat yang besar jika dikuadratkan (X2-X1)^2 akan melebihi batas tipe data `int`. Selalu gunakan `long long`!
2. Loss of Precision: Membandingkan jarak menggunakan `sqrt()` berbahaya karena presisi desimal. Lebih baik membandingkan Jarak Kuadratnya saja tanpa di-akar (yaitu `D^2 = (X2-X1)^2 + (Y2-Y1)^2`) karena tetap berupa bilangan bulat akurat.
Membangun Binary Search Tree
Aturan BST: Nilai baru dimulai dari Root. Jika nilai LEBIH KECIL, pergi ke KIRI. Jika LEBIH BESAR, pergi ke KANAN. Ulangi sampai menemukan tempat kosong (Daun).
⚠️ Common Mistakes: Runtime Error / Null Pointer Exception
Saat melakukan penelusuran (Traversal) pada Tree, siswa pemula sering lupa mengecek kondisi Node Kosong (NULL) sebelum memanggil anak kiri `node->left` atau anak kanan `node->right`. Ini akan menyebabkan program Crash / Runtime Error (Segfault)! Selalu pastikan `if (node == NULL) return;` di awal fungsi rekursi Tree.